package bite;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:【最近公共祖先】
 * 将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意
 * 其祖先也可能是结点本身。
 * User:yxd
 * Date:2022-04-03
 * Time:21:55
 */
public class Day11_2 {
    public static int getLCA(int a, int b) {
        //只要两个数相等了就代表这个就是其的公共父节点,不相等就可以给两个数中较大的值/2求其父节点,直至父节点相等为止
        while(a != b){
            if(a > b){
                a /= 2;
            }else{
                b /= 2;
            }
        }
        return a;
    }
    public static int getLCA1(int a, int b) {
        // write code here
        if(a <= 0 || b <= 0){
            return 0;
        }
        if(a == 1 || b == 1){//有根节点
            return 1;
        }
        Queue<Integer> queue1 = new LinkedList<>();//存放a的路径
        queue1.offer(a);
        while(a != 1){
            if(a % 2 == 1){
                int z = (a - 1) / 2;
                queue1.offer(z);
                a = z;
            }else{
                int z = a / 2;
                queue1.offer(z);
                a = z;
            }
        }
        Queue<Integer> queue2 = new LinkedList<>();//存放b的路径
        queue2.offer(b);
        while(b != 1){
            if(b % 2 == 1){
                int z = (b - 1) / 2;
                queue2.offer(z);
                b = z;
            }else{
                int z = b / 2;
                queue2.offer(z);
                b = z;
            }
        }
        if(queue1.size() > queue2.size()){
            int count = queue1.size() - queue2.size();
            while(count-- != 0){
                queue1.poll();
            }
            while(!queue1.isEmpty() && !queue2.isEmpty()){
                int s1 = queue1.peek();
                int s2 = queue2.peek();
                if(s1 == s2){
                    return (int)s1;
                }
                queue1.poll();
                queue2.poll();
            }
        }else{
            int count = queue2.size() - queue1.size();
            while(count-- != 0){
                queue2.poll();
            }
            while(!queue1.isEmpty() && !queue2.isEmpty()){
                int s1 = queue1.peek();
                int s2 = queue2.peek();
                if(s1 == s2){
                    return (int)s1;
                }
                queue1.poll();

                queue2.poll();
            }
        }
        return 1;
    }

}
